package q754_reachNumber;

public class Solution_1 {
    /*
    到达终点数字
    假设我们移动了 k 次，每次任意地向左或向右移动，那么最终到达的位置实际上就是将 1, 2, 3, ..., k
    这 k 个数添加正号（向右移动）或负号（向左移动）后求和的值
    简单来说，我们要凑出 1+2+3+...+k=target，数值前符号任意。
    我们可以简单的求出sum = 1+2+3+...+k >target的最小的K值。
    这个时候我们可以修改左侧的符号来使得sum==target,每修改一个符号，sum需要减去2数值。
    因为k>(sum-target)/2一定成立，所以当sum-target为偶数时，可以将一个数值的符号改为符号使得等式成立。
    例如 15=1+2+3+4+5>13 (15-13)/2=1 13=-1+2+3+4+5;
    如果sum-target为奇数,那么就需要继续相加来凑出偶数
    例如 15=1+2+3+4+5>12 21=1+2+3+4+5+6>12 28=1+2+3+4+5+6+7>12 (28-12)/2=8
    只要将和为8的数值置负即可 1-2+3+4+5-6+7=12
     */
    public int reachNumber(int target) {
        target = Math.abs(target);
        int k = 0;
        while (target > 0) {
            k++;
            target -= k;
        }
        return target % 2 == 0 ? k : k + 1 + k % 2;
    }
}
